1. Field of the Invention
The following description relates to a distributed Rivest Shamir Adleman (RSA) signature generation method in an ad-hoc network and a node of an ad-hoc network. More particularly, the following description relates to a distributed RSA signature generation method that can generate an RSA signature without interaction among nodes in a distributed RSA signature that distributes a function of a dealer node of a necessary certification authority for management of keys in the ad-hoc network, and can be applied to an additional node corresponding to a new node included in the ad-hoc network, without participation of the dealer node, and a signature generation node for generating an RSA signature.
2. Related Art
Ubiquitous networking indicates that various networks are united based on an Internet Protocol (IP) to provide seamless networking services to a user. When a ubiquitous service is realized using wideband wireless network techniques in the present infrastructure base, problems may arise in that, as users increase, cell range decreases, and expansion of the network infrastructure is needed to overcome the decrease of the cell range. As a result, costs may be increased to maintain the network infrastructure and to build further network infrastructure. Additionally, an entire network may be paralyzed when the network infrastructure fails due to disasters such as war, fire, and flooding. Mobile ad-hoc networks reduce the costs of building the network infrastructure to realize infrastructure-less wireless networking. Features of mobile ad-hoc networks include:                1. Self-organization: All nodes perform functions of a terminal and a router and voluntarily configure the network;        2. Dynamic Topology: Topology of a network changes dynamically due to frequent movements of wireless terminal nodes;        3. Lack of Central Authority: No nodes, or only some nodes, function as a backbone;        4. Lack of Association: It is not easy to control the network (such as controlling node interface and protection against malicious nodes), due to the lack of central authority;        5. No Synchronous Communication: Synchronous communication is impossible due to a feature of the dynamic topology, i.e., when all nodes are simultaneously connected to a network; and        6. Bandwidth and Power Constraints: Limitation on network resources since the network is configured with wireless mobile devices.        
Basically, those security requirements on the ad-hoc network are similar to security requirements on other networks. In the case of an ad-hoc wireless network in a distributed computing environment, the use of encryption keys in unreliable circumstances (such as a fully wireless ad-hoc network) is inevitable. The probability of relying on the encryption keys is increased. Accordingly, it is important to build a reliable relation between the encryption keys, and to distribute the encryption keys to the entire ad-hoc network. A distributed signature scheme based on a public key is one solution to the above problem.
In a distributed signature scheme for secure key distribution, a message is encrypted using a secret key from a reliable certification authority. The encrypted message is decrypted using a public key of the reliable certification authority, and validity is verified. However, all nodes on the network are required to perform the function of the reliable certification authority, since a reliable certification authority does not exist in the ad-hoc network. The distributed signature scheme is based on secret sharing. Secret sharing indicates that secret information, such as a secret key, is shared based on a mathematical algorithm, and the secret information is restored using the shared secret. A Shamir method is one of the representative methods based on a polynomial interpolation for the secret sharing.
Polynomial interpolation is a type of algorithm in which a unique t−1-degree polynomial can be defined when at least t different points exist in a two-dimensional space, i.e. after the t−1-degree polynomial is defined and points in the t−1-degree polynomial are distributed, when at least t points are collected, the original polynomial can be found. Polynomial interpolation is suitable for the secret sharing.
FIG. 1 is a diagram of a conventional distributed RSA signature generation method for secure key distribution among nodes in an ad-hoc network. As shown in FIG. 1, a signature generation node 100 requests neighbor nodes 101 and 102 for secret shares of the neighbor nodes 101 and 102. The neighbor nodes 101 and 102 transmit their own secret shares to the signature generation node 100. The signature generation node 100 can generate the RSA signature using the secret shares of the neighbor nodes 101 and 102.
However, there are problems in that at least t points, i.e., at least t nodes, are required to exist simultaneously when using polynomial interpolation, which means communication (interaction) among shareholders having the t points may occur. As a result, information about the shareholders may be leaked.
FIG. 2 is a diagram of a conventional Shamir's distributed RSA signature method. In order to communicate with a plurality of nodes of an ad-hoc network 200 for an RSA signature, a new node 201 communicates with nodes 202 through 204 of the plurality of nodes. This is considered as essential communication, but is not considered interaction. The nodes 202 through 204, having received the request for the signature from the node 201, collect a partial signature generated using the nodes' 202 through 204 own shares to generate a public key. Generally, identification (ID) information of the nodes 202 through 204 is required when generating the partial signature.
However, the conventional Shamir's distributed RSA signature method has problems in that additional communication, such as collecting information from other nodes to generate the partial signature, may occur, i.e., an interaction 205 may occur, and this may create a security problem. There is another problem in that all nodes are required to simultaneously exist in an environment where topology frequently changes, similar to the ad-hoc network 200. Thus, a non-interactive distributed RSA signature method is needed.